图论基础¶

---

图的存储¶

---

邻接表存图¶

对于每一个节点，记录这个几点连接的所有其他节点和对应权值

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
vector<pair<ll,int> graph[N];//图,{权值,对应的节点}
int n,m;
int main(){
    cin>>n>>m;
    for(int i = 0;i<m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        graph[u].push_back({w,v});
        graph[v].push_back({w,u});
    }
}

---

邻接矩阵存图¶

用一个二维数组记录每两个点之间的距离

两个索引分别代表两个点 g[i][j]的值代表点i和j之间的距离

#define ll long long
const int N = 200010;
const ll INF = 4e18;
ll g[N][N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            if(i==j){
                g[i][j] = 0;//同一个点当然是0
            }else{
                g[i][j] = INF;//初始化矩阵为INF(不可达)
            }
        }
    }
    for(int i = 0;i<m;i++){
        int u,v;
        ll w;
        cin>>u>>v>>w;
        //无向图
        g[u][v] = min(g[u][v],w);
        g[v][u] = min(g[v][u],w);//注意 这里出现重边时取用min是绝大部分情况 不排除其他写法
        //如果是有向图,只用下面这一行
        //g[u][v] = min(g[u][v],w);
    }
}

---

稠密图&稀疏图¶

令n=点数 m=边数

因此无向图最大边数=(n*(n-1))/2

如果m接近于这个最大边数 就是稠密图

如果m接近n或者更小 就是稀疏图

可以根据稀疏和稠密的性质选择算法 获得更高效率

---

最小生成树¶

复杂度

• Prim→O(n^2)

• Prim堆优化→O(m log n)

• Kruskal→O(m log m)

一般来说

• 稠密图->朴素Prim

• 稀疏图->Kruskal或者堆优化Prim

另外:

• 如果n与m很接近(n==m)

选择Kruskal和堆优化Prim在复杂度上没有差异

但是Kruskal是基于sort排序和并查集 更快且不容易写错

选择Kruskal

---